//import gifAnimation.*;
//GifMaker gif;

float x, y;
public static final int amount = 100;
public static ArrayList<Integer> colors = new ArrayList<Integer>(); // 基准下标数组列表
public static int[] numbers = new int[100]; // 待排序数组
public static ArrayList<ArrayList<Integer>> arrIntegers = new ArrayList<ArrayList<Integer>>(); // 二维数组列表，用于存放排序过程

/*初始化待排序数组函数*/
void createNumbers() {
  for (int i = 0; i < numbers.length; ++i) {
    numbers[i] = (int)random(2, amount);
  }
}
/*初始化速写本*/
void setup() {
  size(400, 400);
  background(0);
  createNumbers();
  printArr(numbers);
  QSort(numbers, 0, amount-1);
  println("ColorsSize:"+colors.size());
  println("arrIntegersSize:"+arrIntegers.size());
  printArr(numbers);
  colors.add(colors.get(colors.size()-1));
  //gif = new GifMaker(this, "Qsort1.gif");
  //gif.setRepeat(0); // = loop forever
  //gif.setDelay(0); // 25fps
}
int n = 0, index = 0, speed = 1 ,col = 0;

/*绘制图像*/
void draw() {
  n++;
  noStroke();
  if (n % speed == 0 && index < arrIntegers.size()) {
    background(0); // 设置背景色为黑色
    ArrayList<Integer> arr = arrIntegers.get(index); // 取出对应次数交换后的情况
    if(index < colors.size()){ // 防止最后一帧越界
      col = colors.get(index);
    }
    index++; // 帧数对应下标
    for (int j = 0; j < arr.size(); ++j) {
      x = j * 4;
      y = height - arr.get(j);
      // 为排序块填充颜色
      if(j == col){
        fill(255,0,0);
      }else{
        fill(255,255,255);
      }
      // 绘制排序块
      rect(x, y, 2, arr.get(j), 5);
    }
    // 显示运行时间
    fill(255);
    textSize(20);
    text("Time: " + (millis() - 1) / 1000.0 + "s", 40, 60);
    //text("Time: " + frameCount / 40.0 + "s", 60, 60);
    //gif.addFrame(); //将当前帧写入gif内
  }
}

// 交换函数，用于排序中交换ij的值
public static void Swap(int[] numbers, int i, int j) {
  int tmp    = numbers[j];
  numbers[j] = numbers[i];
  numbers[i] = tmp;
  printArr(numbers);
}

// 快速排序
public static void QSort(int[] numbers, int left, int right) {
  int i, j, k;
  if (left > right) return;
  i = left; j = right;
  k = numbers[left];
  while (i < j) {
    while (k <= numbers[j] && i < j) j--;
    colors.add(k);
    Swap(numbers, i, j);
    while (k >= numbers[i] && i < j) i++;
    colors.add(k);
    Swap(numbers, i, j);
  }
  QSort(numbers, left, i - 1);
  QSort(numbers, j + 1, right);
}

 // 将某一次交换后的状态写入列表
public static void printArr(int[] numbers) {
  ArrayList<Integer> arr = new ArrayList<Integer>();
  for (int i = 0; i < numbers.length; ++i) {
    arr.add(numbers[i]);
  }
  arrIntegers.add(arr);
}
